package datastructure.unionfind;

/**
 * @author wangmaolin1
 * @date 2023/11/13 21:18
 */
public class UF2 {
    private int count;
    private int[] parent;
    private int[] weight;

    public void UF2(int n) {
        count = n;
        parent = new int[n];
        weight = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            weight[i]=1;
        }
    }

    public void  union(int p,int q){
        int rootP = find(p);
        int rootQ = find(q);
        if(rootP!=rootQ){
            if (weight[rootP]>weight[rootQ]){
                parent[rootQ]=rootP;
                weight[rootP]+=weight[rootQ];
            }else {
                parent[rootP]=rootQ;
                weight[rootQ]+=weight[rootP];

            }
            count--;
        }
    }

    private int find(int x) {
        int root = x;
        while (parent[root]!=root){
            root= parent[root];
        }
        int tempX=parent[x];
        while (x!=root){
            parent[x] = root;
            x=tempX;
            tempX=parent[tempX];
        }
        return root;
    }

    public int count(){
        return count;
    }
    public boolean connected(int p ,int q){
        return find(p) == find(q);
    }

}
